package com.fastadmin.skill;

import java.util.Arrays;

/**
 * 有一个机器按自然数序列的方式吐出球(1 号球,2 号球,3 号球,......)，
 * 你有一个袋子，袋子最多只能装下K个球，并且除袋子以外，你没有更多的空间。
 * 设计一种选择方式，使得当机器吐出第N号球的时候(N>K)，你袋子中的球数是K个，
 * 同时可以保证从1号球到N号球中的每一个，被选进袋子的概率都是K/N。
 * 举一个更具体的例子。有一个只能装下10个球的袋子，当吐出100个球时，袋子里有10个球，
 * 并且1~100号中的每一个球被选中的概率都是10/100。
 * 然后继续吐球，当吐出1000个球时，袋子里有10个球，并且1~1000号中的每一个球被选中的概率都是10/1000。
 * 继续吐球，当吐出i个球时，袋子里有10个球，并且1~i号中的每一个球被选中的概率都是10/i，
 * 即吐球的同时，已经吐出的球被选中的概率也动态地变化。
 * @author Andy
 *
 */
public class _腾讯面试_设计抽奖系统 {
	/**
	 * 就是抽奖问题，在用户登录系统的时候就确定其是否被抽中。
	 * 蓄水池问题#牛客堂直播视频#常见面试题精讲（六）（9.16）
	 * 分两部分考虑，前k个球和k+1～N个球两部分。
	 * 一，下面先证明前k个球中奖概率为k/N。
	 * 前k个球直接进袋子，因为当前i<k时一定选中它，即当前时刻以1的概率存在于袋子中。
	 * 接下来我们考虑第k+1个球，那么它有k/k+1的概率会被选中进袋子(k/N)，……(1)
	 * 那么袋子中有球a会被选中出袋子的概率为1/k，…………………………………………………………(2)
	 * 故a球出袋子的概率为p0=1*(1/k)*(k/k+1)= 1/k+1 ,事件(1)(2)同时发生
	 * 所以球a留下来（中奖）的概率为1-p0=k/k+1.//这里说明前k个球最终被选中的概率为1/k+1
	 * 下面考虑k+2号球，一样的可求得k+1/k+2的概率保证球a中奖，
	 * 直到N号球N-1/N的概率保证球a中奖。
	 * 最终球a中奖的概率为1×(k/k+1)×(k+1/k+2)×……×(N-1/N)=k/N。
	 * 
	 * 二，下面先证明前k+1～N个球中奖概率为k/N。
	 * k+1号球进袋子的概率为k/k+1,这里袋子中哪个球出袋子第k+1号球并不关心，
	 * 下面的过程同上，要保证k+1号球中奖，即k+2～N号球不能进袋子，
	 * 计算如下(k/k+1)*(k+1/k+2)*...*(N-1/N)=k/N。
	 * 可以看到所有球中奖的概率都相同，均为k/N。
	 */
	//一个简单的随机函数，决定一个事情做还是不做
	public static int rand(int max) {
		return (int) (Math.random() * max) + 1;
	}

	public static int[] getKNumsRand(int k, int max) {
		if (max < 1 || k < 1)
			return null;
		int[] res = new int[Math.min(k, max)];
		for (int i = 0; i < res.length; i++) {
			res[i] = i + 1;// 前K个数直接进袋子
		}
		for (int i = k + 1; i < max + 1; i++) {
			if (rand(i) <= k) {// 决定第i个球进不进袋子
				res[rand(k) - 1] = i;// i随机替掉袋子中的一个
			}
		}
		return res;
	}
	
	public static void main(String ...strings){
		System.out.println(Arrays.toString(getKNumsRand(5, 100)));
	}
}
